package cumt.oj;

/**
 * @Author Fizz Pu
 * @Date 2020/10/16 下午3:16
 * @Version 1.0
 * 失之毫厘，缪之千里！
 */

import java.util.*;

/**
 * 题目描述
 * 给定n个矩阵{A1,A2,...,An}，及m个矩阵连乘的表达式，判断每个矩阵连乘表达式是否满足矩阵乘法法则，
 * 如果满足，则计算矩阵的最小连乘次数，如果不满足输出“MengMengDa“。
 *
 * 输入
 * 输入数据由多组数据组成（不超过10组样例）。每组数据格式如下：
 * 第一行是2个整数n (1≤n≤26)和m(1≤m≤3)，表示矩阵的个数。
 * 接下来n行，每行有一个大写字母，表示矩阵的名字，后面有两个整数r和c，分别表示该矩阵的行数和列数，其中1<r, c<100。
 * 第n+1行到第n+m行，每行是一个矩阵连乘的表达式(2<=矩阵个数<=100)。
 *
 * 输出
 * 对于每个矩阵连乘表达式，如果运算不满足矩阵乘法法则的情况（即左矩阵列数与右矩阵的行数不同），则输出“MengMengDa”，否则输出最小矩阵连乘次数。
 *
 * 数据保证结果不超过1e9。
 * 样例输入
 * 3 2
 * A 10 100
 * B 5 50
 * C 100 5
 * ACB
 * ABC
 * 样例输出
 * 7500
 * MengMengDa
 */

// 和树上将的类似
// 可以划分子问题
// dp[i][j] = dp[i][k] + dp[k+1][j] + Ai的行 * Ak的列* Aj的列
// 连乘前首先判断是否可以连乘 Ai* Aj判断i的列是否等于j的列

// 快速利用矩阵的名字找到矩阵的行和列，采用map结构{“A”:[10,100]}
// 存在bug没找到，测试通不过
public class Matrix {
    public static int MAX =  0x3f3f3f3f;
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int matrixNumbers = scanner.nextInt();
        int testNumbers = scanner.nextInt();
        Map<Character, List<Integer>> matrixInfo = new HashMap<>(); // {"A":[row, column]}

        for (int i = 0; i < matrixNumbers; ++i) {
            String martrixName = scanner.next();
            int row = scanner.nextInt();
            int column = scanner.nextInt();
            ArrayList<Integer> list = new ArrayList<>();
            list.add(row);
            list.add(column);
            matrixInfo.put(martrixName.charAt(0), list);
        }

        for (int j = 0; j < testNumbers; ++j) {
            String expression = scanner.next();
            try {
                System.out.println(printMin(matrixInfo, expression, matrixNumbers));
            } catch (Exception e) {
                System.out.println("MengMengDa");
            }
        }
    }
        private static long  printMin(Map<Character, List<Integer>> matrixInfo, String exp, int matrixNumber) throws Exception{
            int[][]  dp = new int[matrixNumber][matrixNumber];
            for(int  m = 0; m < matrixNumber; ++m)dp[m][m] = 0;

            for(int i = 2; i <= matrixNumber; ++i){ // 矩阵长度, 1的地方已经被初始化为了0
                for(int row = 1; row <= matrixNumber; ++row){
                    int col = row + i - 1;
                    if(col > matrixNumber)break;
                    dp[row-1][col-1] = MAX;
                    char start = exp.charAt(row-1);
                    char end = exp.charAt(col-1);
                    int startrow = matrixInfo.get(start).get(0);
                    int startcol = matrixInfo.get(start).get(1);
                    int endrow = matrixInfo.get(end).get(0);
                    int endcol = matrixInfo.get(end).get(1);

                    if(i == 2){
                        if(startcol != endrow){
                            throw  new Exception("error");
                        }
                        dp[row-1][col-1] = Math.min(startrow * startcol * endcol, MAX);
                    } else {
                        for (int k = row; k < col; ++k) {
                            char kchar = exp.charAt(k - 1);
                            int kCol = matrixInfo.get(kchar).get(1);
                            dp[row-1][col-1] = Math.min(dp[row - 1][k - 1] + dp[k][col - 1] + startrow * endcol * kCol, dp[row-1][col-1]);
                        }
                    }
                }
            }
            return dp[0][matrixNumber-1];
    }
}
